package 数据结构OJ;

public class 逆置单链表_02 {

     // Definition for singly-linked list.
      public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }

    class Solution {
        public ListNode reverseList(ListNode head) {
            //判断头是否合法，是否只有一个节点
            if((head == null) || (head.next == null)) {
                return head;
            }
            //prev为新链表的指针
            ListNode prev = null;
            //cur为旧链表的指针
            ListNode cur = head;
            while(cur != null) {
                //temp负责保存正在改变指针方向的节点
                //保存cur节点
                ListNode temp = cur;
                //cur节点指向旧链表的下一个
                cur = cur.next;
                //temp节点与原来链表断开，指向新链表prev
                temp.next = prev;
                //将prev的头指针更新
                // 更新为新的头节点temp
                prev = temp;
            }
            //返回新的逆置后的链表
            return prev;

//          递归解法


//            if(head == null || head.next == null) {
//                return head;
//            }
//            ListNode newHead = reverseList(head.next); //一直循环到链尾
//            head.next.next = head;                       //翻转链表的指向
//            head.next = null;                          //记得赋值，防止链表错乱
//            return newHead;


        }
    }
//            ListNode dummyHead = new ListNode(0);
//            dummyHead.next = head;
//            //如果头结点为空或链表只有一个节点，直接返回head
//            if(head == null || head.next == null) {
//                return head;
//            }else {
//                ListNode f = dummyHead.next;
//                ListNode s = f.next;
//                while(s != null){
//                    //下次迭代的位置
//                    f.next = s.next;
//                    s.next = dummyHead.next;
//                    dummyHead.next = s;
//                    s = f.next;
//                }
//
//                return dummyHead.next;
//            }
//        }
//    }
}
